package leetcode.year2021.month11;

import java.util.Arrays;
import java.util.Random;

// 215. 数组中的第K个最大元素
public class _03_1FindKthLargest215 {
  Random random = new Random();

  public int findKthLargest(int[] nums, int k) {
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
  }
  public int quickSelect(int[] a, int l, int r, int index) {
    int q = randomPartition(a, l, r);
    if (q == index) {
      return a[q];
    } else {
      return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
    }
  }

  public int randomPartition(int[] a, int l, int r) {
    int i = random.nextInt(r - l + 1) + l;
    swap(a, i, r);
    return partition(a, l, r);
  }

  public int partition(int[] a, int l, int r) {
    int x = a[r], i = l - 1;
    for (int j = l; j < r; ++j) {
      if (a[j] <= x) {
        swap(a, ++i, j);
      }
    }
    swap(a, i + 1, r);
    return i + 1;
  }

  public void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }
//  2、使用排序工具进行的排序，只用了2ms
//  public int findKthLargest(int[] nums, int k) {
//    Arrays.sort(nums);
//    return nums[nums.length - k];
//  }
  //1、 自己写的快速排序算法，稀烂
//  public int findKthLargest(int[] nums, int k) {
//    qsortImpl(nums,0,nums.length-1);
//    return nums[nums.length-k];
//  }
//
//  public int[] qsortImpl(int arr[], int start, int end){
//    int scalar = arr[start];
//    int i = start;
//    int j = end;
//    while (i < j){
//      if (arr[i] < scalar) {
//        i++;
//      }
//      if (arr[j] > scalar){
//        j--;
//      }
//      if (arr[i] == arr[j] && i < j){
//        i++;
//      } else {
//        int temp = arr[i];
//        arr[i] = arr[j];
//        arr[j] = temp;
//      }
//    }
//    if (i > start) {
//      arr = qsortImpl(arr,start, i-1);
//    }
//    if (j < end){
//      arr = qsortImpl(arr,i+1, end);
//    }
//    return arr;
//  }

  /**
   * 215. 数组中的第K个最大元素
   * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
   *
   * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
   *
   *
   *
   * 示例 1:
   *
   * 输入: [3,2,1,5,6,4] 和 k = 2
   * 输出: 5
   * 示例 2:
   *
   * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
   * 输出: 4
   *
   *
   * 提示：
   *
   * 1 <= k <= nums.length <= 104
   * -104 <= nums[i] <= 104
   */
}
